#include "FDR.h"
#include"global.h"
#include"function.h"

FDR::FDR(void)
{
}


FDR::~FDR(void)
{
}

unordered_map<int,string> FDR::_Dic;

string FDR::_Run(int size)
{
	if(_Dic.find(size)!=_Dic.end())
		return _Dic.at(size);
	int group=int(ceil((log(size+3.0)/log(2.0)-1)));
	string _runcode;
	for(int i=1;i<group;i++)
		_runcode+='1';
	_runcode+='0';

	int tail=size-(1<<group)+2;
	for(int i=group-1;i>=0;i--)
		_runcode+=((tail>>i)&1)+'0';
	_Dic.insert(make_pair(size,_runcode));
	return _runcode;
}

unique_ptr<string> FDR::_Code(const string& data)
{
	unique_ptr<string> fdr(new string);
	try{
	for(uint32_t i=0;i<data.length();i++)
	{
		int l=0;
		while(i<data.length()&&data.at(i)!='1')
		{
			i++;
			l++;
		}
		*fdr+=_Run(l);
	}
	}catch(msg &e){simpleio::error("FDR::_Code ",e);}
	return fdr;
}

unique_ptr<string> FDR::code(const string& data)
{
	return _Code(data);
}

unique_ptr<string> FDR::code_xor(const string& data)
{
	string _data=data;
	if(_data[0]=='X')_data[0]='0';
	for(uint32_t i=1;i<_data.size();i++)
		if(_data[i]=='X')
			_data[i]=_data[i-1];
	for(uint32_t i=_data.size()-1;i>=1;i--)
		if(_data[i]==_data[i-1])
			_data[i]='0';
		else
			_data[i]='1';
	return _Code(_data);
}

int FDR::_Cost(const string& str1,const string& str2)
{
	const int X_COST=5;
	int _c=0;
	for(uint32_t i=0;i<str1.size();i++)
		if(str1[i]!=str2[i])
		{
			if(str1[i]=='X'||str2[i]=='X')
				_c+=X_COST;
			else
				_c+=10;
		}
		else if(str1[i]=='X')
			_c+=X_COST;
	return _c;
}

string FDR::reorder(const vector<string>& data)
{
	matrix<int> graph(data.size(),data.size());
	for(uint32_t i=0;i<data.size()-1;i++)
		for(uint32_t j=i+1;j<data.size();j++)
			graph(i,j)=graph(j,i)=_Cost(data[i],data[j]);
	//minimum spanning tree
	unique_ptr<int[]> cost(new int[data.size()]);
	unique_ptr<int[]> parent(new int[data.size()]);
	parent[0]=-1;
	for(uint32_t i=1;i<data.size();i++)
	{
		cost[i]=graph(0,i);
		parent[i]=0;
	}
	cost[0]=INT_MAX;
	for(uint32_t i=0;i<data.size()-1;i++)
	{
		int p=min_element(cost.get(),cost.get()+data.size())-cost.get();
		cost[p]=INT_MAX;
		for(uint32_t j=1;j<data.size();j++)
			if(cost[j]!=INT_MAX&&graph(j,p)<cost[j])
			{
				cost[j]=graph(j,p);
				parent[j]=p;
			}
	}
	//turn tree to binary tree
	unique_ptr<int[]> lchild(new int[data.size()]);
	unique_ptr<int[]> rbrother(new int[data.size()]);
	for(uint32_t i=0;i<data.size();i++)
	{
		lchild[i]=-1;
		rbrother[i]=-1;
	}
	for(uint32_t i=1;i<data.size();i++)
	{
		if(lchild[parent[i]]==-1)
			lchild[parent[i]]=i;
		else
		{
			int brother=lchild[parent[i]];
			while(rbrother[brother]!=-1)
				brother=rbrother[brother];
			rbrother[brother]=i;
		}
	}
	//travels
	stack<int> _stack;
	vector<int> _vector;
	_stack.push(0);
	while(!_stack.empty())
	{
		int cur=_stack.top();
		_stack.pop();
		_vector.push_back(cur);
		//if(rbrother[cur]!=-1)
		//_stack.push(rbrother[cur]);
		//if(lchild[cur]!=-1)
		//_stack.push(lchild[cur]);
		int child=lchild[cur];
		while(child!=-1)
		{
			_stack.push(child);
			child=rbrother[child];
		}
	}
	//for(int i=0;i<_vector.size();i++)
	//_vector[i]=i;
	//generate string
	string _string;
	vector<string> _testset;
	_string=data[_vector[0]];
	for(uint32_t i=0;i<_string.length();i++)
		if(_string[i]=='X')
			_string[i]='0';
	_testset.push_back(_string);
	for(uint32_t i=1;i<_vector.size();i++)
	{
		int p=_vector[i];
		for(uint32_t j=0;j<_string.length();j++)
			if(data[p][j]!='X')
				_string[j]=data[p][j];
		_testset.push_back(_string);
	}
	//string u;
	//for(int i=0;i<_testset.size();i++)
	//	u+=_testset[i]+'\n';
	//simpleio::output("aa",u);
	int length=_string.length();
	_string=_testset[0];
	for(uint32_t i=1;i<_testset.size();i++)
		for(int j=0;j<length;j++)
			if(_testset[i-1][j]==_testset[i][j])
				_string+='0';
			else
				_string+='1';

	return _string;
}

string FDR::reorder2(const vector<string>& data)
{
	uint32_t size=data.at(0).length();
	matrix<int> graph(size,size);
	try{
		for(uint32_t i=0;i<size-1;i++)
			for(uint32_t j=i+1;j<size;j++)
			{
				const int X_COST=5;
				int _c=0;
				for(uint32_t k=0;k<data.size();k++)
					if(data.at(k).at(i)!=data.at(k).at(j))
					{
						if(data[k][i]=='X'||data[k][j]=='X')
							_c+=X_COST;
						else
							_c+=10;
					}
					else if(data[k][i]=='X')
						_c+=X_COST;
				graph(i,j)=graph(j,i)=_c;
			}
	}catch(msg &e)
	{
		simpleio::error("reorder2 initial:",e);
	}
	//minimum spanning tree
	unique_ptr<int[]> cost(new int[size]);
	unique_ptr<int[]> parent(new int[size]);
	parent[0]=-1;
	for(uint32_t i=1;i<size;i++)
	{
		cost[i]=graph(0,i);
		parent[i]=0;
	}
	cost[0]=INT_MAX;
	for(uint32_t i=0;i<size-1;i++)
	{
		int p=min_element(cost.get(),cost.get()+size)-cost.get();
		cost[p]=INT_MAX;
		for(uint32_t j=1;j<size;j++)
			if(cost[j]!=INT_MAX&&graph(j,p)<cost[j])
			{
				cost[j]=graph(j,p);
				parent[j]=p;
			}
	}
	//turn tree to binary tree
	unique_ptr<int[]> lchild(new int[size]);
	unique_ptr<int[]> rbrother(new int[size]);
	for(uint32_t i=0;i<size;i++)
	{
		lchild[i]=-1;
		rbrother[i]=-1;
	}
	for(uint32_t i=1;i<size;i++)
	{
		if(lchild[parent[i]]==-1)
			lchild[parent[i]]=i;
		else
		{
			int brother=lchild[parent[i]];
			while(rbrother[brother]!=-1)
				brother=rbrother[brother];
			rbrother[brother]=i;
		}
	}
	//travels
	stack<int> _stack;
	vector<int> _vector;
	_stack.push(0);
	while(!_stack.empty())
	{
		int cur=_stack.top();
		_stack.pop();
		_vector.push_back(cur);
		//if(rbrother[cur]!=-1)
		//_stack.push(rbrother[cur]);
		//if(lchild[cur]!=-1)
		//_stack.push(lchild[cur]);
		int child=lchild[cur];
		while(child!=-1)
		{
			_stack.push(child);
			child=rbrother[child];
		}
	}
	if(_vector.size()!=size)
		throw msg("invalid travels");
	//generate string
	vector<string> _testset=data;
	for(uint32_t j=0;j<size;j++)
		for(uint32_t i=0;i<data.size();i++)
			_testset[i][j]=data[i][_vector[j]];
	/*
	//vector reorder
	for(uint32_t i=0;i<size;i++)
	if(_testset[0][i]=='X')
	_testset[0][i]='0';
	for(uint32_t i=1;i<_testset.size();i++)
	{
	for(uint32_t j=0;j<size;j++)
	if(_testset[i][j]=='X')
	_testset[i][j]=_testset[i-1][j];
	}
	for(uint32_t i=_testset.size()-1;i>=1;i--)
	for(uint32_t j=0;j<size;j++)
	if(_testset[i-1][j]==_testset[i][j])
	_testset[i][j]='0';
	else
	_testset[i][j]='1';
	*/
	string _str;
	for(auto &e:_testset)
		_str+=e;
	return _str;
}

//----------------------Generic Algorithms-----------------

const int POPULATION_SIZE=20;
const double PROBABILITY_SWAP=0000;
const double PROBABILITY_SHIFT=10000;
const int LOOPS=3000;

struct Individual
{
	vector<int> data;//vector squence
	int value;//adapt degree
};

//Global varibLe
//random generator
random_device rd;
mt19937 gen(rd());

//adapt up
inline 	int adapt_up(const vector<string>& data,const vector<int>& idx,int pos)
{
	if(pos==0)return 0;
	int sum=0;
	int length=data.front().length();
	for(int j=0;j<length;j++)
	{
		if(data.at(idx.at(pos)).at(j)=='X')
			continue;
		int i=pos-1;
		while(i>=1&&data.at(idx.at(i)).at(j)=='X')
			i--;
		if(data.at(idx.at(i)).at(j)!='X'&&data.at(idx.at(i)).at(j)!=data.at(idx.at(pos)).at(j))
			sum++;
	}
	return sum;
}

inline	int adapt_down(const vector<string>& data,const vector<int>& idx,int pos)
{
	if(pos==data.size()-1||pos==-1)return 0;
	int sum=0;
	try{
	int length=data.front().length();
	string str=data.at(idx.at(pos));
	for(int j=0;j<length;j++)
	{
		uint32_t i=pos;
		try{
		while(i>=1&&data.at(idx.at(i)).at(j)=='X')
			i--;
		if(data.at(idx.at(i)).at(j)!='X')
		{
			if(str.at(j)=='X')
				str.at(j)=data.at(idx.at(i)).at(j);
		}
		i=pos+1;
		}catch(msg &e){simpleio::error("down1 ",e);}
		try{
		while(i<data.size()-1&&data.at(idx.at(i)).at(j)=='X')
			i++;
		char c1=str.at(j);
		char c2=data.at(idx.at(i)).at(j);
		if(c1!='X'&&c2!='X'&&c1!=c2)
			sum++;
		}catch(msg &e){simpleio::error("down2 ",e);}
	}
	}catch(msg& e){simpleio::error("adapt_down:",e);}
	return sum;
}

inline	int adapt_updown(const vector<string>& data,const vector<int>& idx,int pos)
{
	int sum=0;
	try{
	if(pos<0)return 0;
	int length=data.front().length();
	string str=data.at(idx.at(pos));
	for(int j=0;j<length;j++)
	{
		uint32_t i;
		if(pos!=0){
		i=pos-1;
		while(i>=1&&data.at(idx.at(i)).at(j)=='X')
			i--;
		if(data.at(idx.at(i)).at(j)!='X')
		{
			if(str.at(j)=='X')
				str.at(j)=data.at(idx.at(i)).at(j);
			else if(str.at(j)!=data.at(idx.at(i)).at(j))
				sum++;
		}
		}
		if(pos!=data.size()-1){
		i=pos+1;
		while(i<data.size()-1&&data.at(idx.at(i)).at(j)=='X')
			i++;
		char c1=str.at(j);
		char c2=data.at(idx.at(i)).at(j);
		if(c1!='X'&&c2!='X'&&c1!=c2)
			sum++;
		}
	}
	}catch(msg &e){simpleio::error("updown",e);}
	return sum;
}

inline int adapt_all(const vector<string>& data,const vector<int>& idx)
{
	int sum=0;
	for(uint32_t j=1;j<idx.size();j++)
		sum+=adapt_up(data,idx,j);
	return sum;
}

inline void swap(const vector<string>& data,Individual& ind)
{
	try{
	uniform_int_distribution<> dis(0,data.size()-1);
	//cout<<"before swap:"<<adapt_all(data,ind.data)<<endl;
	int p1=dis(gen);
	int p2=dis(gen);
	//int pre=adapt_updown(data,ind.data,p2)+adapt_updown(data,ind.data,p1);
	swap(ind.data.at(p1),ind.data.at(p2));
	//int now=adapt_updown(data,ind.data,p1)+adapt_updown(data,ind.data,p2);
	//ind.value+=now-pre;
	//cout<<"pre and now:"<<pre<<" "<<now<<" "<<ind.value<<endl;
	//cout<<"after swap:"<<adapt_all(data,ind.data)<<endl;
	}catch(msg& e){simpleio::error("swap:",e);}
}

inline 	void shift(const vector<string>& data,Individual& ind)
{
	try{
	uniform_int_distribution<> dis(0,data.size()-1);
	//cout<<"before shift:"<<adapt_all(data,ind.data)<<endl;
	int p1=dis(gen);
	int p2=dis(gen);
	if(p1==p2)return;
	//int pre;
	try{
	//pre=adapt_updown(data,ind.data,p2)+adapt_down(data,ind.data,p1-1);
	}catch(msg& e){simpleio::error("shift pre:",e);}
	if(p1<p2)
	{
		int t=ind.data.at(p2);
		int i=p2;
		while(i>p1)
		{
			ind.data.at(i)=ind.data.at(i-1);
			i--;
		}
		ind.data.at(p1)=t;
	}
	else if(p1>p2)
	{
		int t=ind.data.at(p2);
		int i=p2;
		while(i<p1)
		{
			ind.data.at(i)=ind.data.at(i+1);
			i++;
		}
		ind.data.at(p1)=t;
	}
	//int now;
	try{
	//now=adapt_down(data,ind.data,p2)+adapt_updown(data,ind.data,p1);
	}catch(msg& e){simpleio::error("shift now:",e);}
	//ind.value+=now-pre;
	//cout<<"pre and now:"<<pre<<" "<<now<<" "<<ind.value<<endl;
	//cout<<"after shift:"<<adapt_all(data,ind.data)<<endl;
	}catch(msg& e){simpleio::error("shift:",e);}

}

string FDR::reorder_GA(const vector<string>& data)
{
	vector<Individual> population;
	//initial Population
	Individual ind;
	for(uint32_t i=0;i<data.size();i++)
		ind.data.push_back(i);
	ind.value=adapt_all(data,ind.data);
	population.push_back(ind);
	for(uint32_t i=0;i<POPULATION_SIZE-1;i++)
	{
		/*
		//random permutation
		for(uint32_t j=0;j<data.size();j++)
		{
			uniform_int_distribution<> dis(j,data.size()-1);
			swap(ind.data.at(i),ind.data.at(dis(gen)));
		}*/
		//swap(data,ind);
		shift(data,ind);
		//adapt value
		ind.value=adapt_all(data,ind.data);
		population.push_back(ind);
	}
	uniform_int_distribution<> dis(1,10000);
	vector<Individual> childs;
	int num=LOOPS;
	while(num--)
	{
		if(population.size()!=POPULATION_SIZE)
			throw msg("population size error");
		childs.clear();
		for(auto p=population.begin();p!=population.end();p++)
		{
			//swap
			Individual ind=*p;
			if(dis(gen)<=PROBABILITY_SWAP)
				swap(data,ind);
			//shift
			if(dis(gen)<=PROBABILITY_SHIFT)
			 	shift(data,ind);
			ind.value=adapt_all(data,ind.data);
			childs.push_back(ind);
		}
		childs.insert(childs.end(),population.begin(),population.end());
		population.clear();
		//select
		/*
		auto maxp=childs.begin();
		auto p=maxp;
		int sum=p->value;
		for(p++;p!=childs.end();p++)
		{
			sum+=p->value;
			if(p->value>maxp->value)
				maxp=p;
		}
		sum=POPULATION_SIZE*2*maxp->value-sum+POPULATION_SIZE*2;//+1
		vector<tuple<list<Individual>::iterator,int>> wh;
		int pr=0;
		for(auto p=childs.begin();p!=childs.end();p++)
		{
			pr+=10000*(maxp->value-p->value+1)/sum;//+1
			wh.push_back(make_tuple(p,pr));
		}
		for(int i=0;i<POPULATION_SIZE;i++)
		{
			for(auto p=wh.begin();p!=wh.end();p++)
				if(dis(gen)<=get<1>(*p))
				{
					population.push_back(*get<0>(*p));
					break;
				}
		}*/
		for(int i=0;i<POPULATION_SIZE;i++){
		uniform_int_distribution<> cp(0,POPULATION_SIZE*2-1);
		int p1=cp(gen);
		int p2=cp(gen);
		if(childs.at(p1).value<childs.at(p2).value)
			population.push_back(childs.at(p1));
		else
			population.push_back(childs.at(p2));
		}

	}
	auto sp=population.begin();
	for(auto p=population.begin();p!=population.end();p++)
	{
		if(p->value<sp->value)
			sp=p;
		//cout<<p->value<<endl;
	}
	auto col=sp->data;
	//GA end
	string _string;
	vector<string> _testset;
	_string=data.at(col.front());
	for(uint32_t i=0;i<_string.length();i++)
		if(_string[i]=='X')
			_string[i]='0';
	_testset.push_back(_string);
	for(uint32_t i=1;i<col.size();i++)
	{
		int p=col.at(i);
		for(uint32_t j=0;j<_string.length();j++)
			if(data[p][j]!='X')
				_string[j]=data[p][j];
		_testset.push_back(_string);
	}
	int length=_string.length();
	_string=_testset[0];
	for(uint32_t i=1;i<_testset.size();i++)
		for(int j=0;j<length;j++)
			if(_testset[i-1][j]==_testset[i][j])
				_string+='0';
			else
				_string+='1';

	return _string;
}

//--------------------end Generic Algorithms-----------------

unique_ptr<string> FDR::code_ghost(const string& data)
{
	unique_ptr<string> fdr(new string);
	bool ghost;
	try{
	for(uint32_t i=0;i<data.length();i++)
	{
		int l=0;
		ghost=false;
		while(i<data.length()&&data.at(i)!='1')
		{
			i++;
			l++;
		}
		if(l==0)
		{
			int p1=i-2;
			int p2=i+1;
			while(p1>=0&&(uint32_t)p2<data.length()&&data.at(p1)!='1'&&data.at(p2)!='1')
			{
				p1--;
				p2++;
			}
			if(p1>=0&&(uint32_t)p2<data.length()&&data.at(p1)=='1')
			{
				*fdr+="0";
				i=p2-1;
				ghost=true;
			}
		}
		if(!ghost)
		*fdr+=_Run(l+2);
	}
	}catch(msg &e){simpleio::error("FDR::code_ghost ",e);}
	return fdr;
}
